home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / python2.4 / site-packages / Crypto / PublicKey / DSA.py < prev    next >
Text File  |  2006-06-22  |  7KB  |  239 lines
  1.  
  2. #
  3. #   DSA.py : Digital Signature Algorithm
  4. #
  5. #  Part of the Python Cryptography Toolkit
  6. #
  7. # Distribute and use freely; there are no restrictions on further
  8. # dissemination and usage except those imposed by the laws of your
  9. # country of residence.  This software is provided "as is" without
  10. # warranty of fitness for use or suitability for any purpose, express
  11. # or implied. Use at your own risk or not at all.
  12. #
  13.  
  14. __revision__ = "$Id: DSA.py,v 1.16 2004/05/06 12:52:54 akuchling Exp $"
  15.  
  16. from Crypto.PublicKey.pubkey import *
  17. from Crypto.Util import number
  18. from Crypto.Util.number import bytes_to_long, long_to_bytes
  19. from Crypto.Hash import SHA
  20.  
  21. try:
  22.     from Crypto.PublicKey import _fastmath
  23. except ImportError:
  24.     _fastmath = None
  25.  
  26. class error (Exception):
  27.     pass
  28.  
  29. def generateQ(randfunc):
  30.     S=randfunc(20)
  31.     hash1=SHA.new(S).digest()
  32.     hash2=SHA.new(long_to_bytes(bytes_to_long(S)+1)).digest()
  33.     q = bignum(0)
  34.     for i in range(0,20):
  35.         c=ord(hash1[i])^ord(hash2[i])
  36.         if i==0:
  37.             c=c | 128
  38.         if i==19:
  39.             c= c | 1
  40.         q=q*256+c
  41.     while (not isPrime(q)):
  42.         q=q+2
  43.     if pow(2,159L) < q < pow(2,160L):
  44.         return S, q
  45.     raise error, 'Bad q value generated'
  46.  
  47. def generate(bits, randfunc, progress_func=None):
  48.     """generate(bits:int, randfunc:callable, progress_func:callable)
  49.  
  50.     Generate a DSA key of length 'bits', using 'randfunc' to get
  51.     random data and 'progress_func', if present, to display
  52.     the progress of the key generation.
  53.     """
  54.  
  55.     if bits<160:
  56.         raise error, 'Key length <160 bits'
  57.     obj=DSAobj()
  58.     # Generate string S and prime q
  59.     if progress_func:
  60.         progress_func('p,q\n')
  61.     while (1):
  62.         S, obj.q = generateQ(randfunc)
  63.         n=(bits-1)/160
  64.         C, N, V = 0, 2, {}
  65.         b=(obj.q >> 5) & 15
  66.         powb=pow(bignum(2), b)
  67.         powL1=pow(bignum(2), bits-1)
  68.         while C<4096:
  69.             for k in range(0, n+1):
  70.                 V[k]=bytes_to_long(SHA.new(S+str(N)+str(k)).digest())
  71.             W=V[n] % powb
  72.             for k in range(n-1, -1, -1):
  73.                 W=(W<<160L)+V[k]
  74.             X=W+powL1
  75.             p=X-(X%(2*obj.q)-1)
  76.             if powL1<=p and isPrime(p):
  77.                 break
  78.             C, N = C+1, N+n+1
  79.         if C<4096:
  80.             break
  81.         if progress_func:
  82.             progress_func('4096 multiples failed\n')
  83.  
  84.     obj.p = p
  85.     power=(p-1)/obj.q
  86.     if progress_func:
  87.         progress_func('h,g\n')
  88.     while (1):
  89.         h=bytes_to_long(randfunc(bits)) % (p-1)
  90.         g=pow(h, power, p)
  91.         if 1<h<p-1 and g>1:
  92.             break
  93.     obj.g=g
  94.     if progress_func:
  95.         progress_func('x,y\n')
  96.     while (1):
  97.         x=bytes_to_long(randfunc(20))
  98.         if 0 < x < obj.q:
  99.             break
  100.     obj.x, obj.y = x, pow(g, x, p)
  101.     return obj
  102.  
  103. def construct(tuple):
  104.     """construct(tuple:(long,long,long,long)|(long,long,long,long,long)):DSAobj
  105.     Construct a DSA object from a 4- or 5-tuple of numbers.
  106.     """
  107.     obj=DSAobj()
  108.     if len(tuple) not in [4,5]:
  109.         raise error, 'argument for construct() wrong length'
  110.     for i in range(len(tuple)):
  111.         field = obj.keydata[i]
  112.         setattr(obj, field, tuple[i])
  113.     return obj
  114.  
  115. class DSAobj(pubkey):
  116.     keydata=['y', 'g', 'p', 'q', 'x']
  117.  
  118.     def _encrypt(self, s, Kstr):
  119.         raise error, 'DSA algorithm cannot encrypt data'
  120.  
  121.     def _decrypt(self, s):
  122.         raise error, 'DSA algorithm cannot decrypt data'
  123.  
  124.     def _sign(self, M, K):
  125.         if (K<2 or self.q<=K):
  126.             raise error, 'K is not between 2 and q'
  127.         r=pow(self.g, K, self.p) % self.q
  128.         s=(inverse(K, self.q)*(M+self.x*r)) % self.q
  129.         return (r,s)
  130.  
  131.     def _verify(self, M, sig):
  132.         r, s = sig
  133.         if r<=0 or r>=self.q or s<=0 or s>=self.q:
  134.             return 0
  135.         w=inverse(s, self.q)
  136.         u1, u2 = (M*w) % self.q, (r*w) % self.q
  137.         v1 = pow(self.g, u1, self.p)
  138.         v2 = pow(self.y, u2, self.p)
  139.         v = ((v1*v2) % self.p)
  140.         v = v % self.q
  141.         if v==r:
  142.             return 1
  143.         return 0
  144.  
  145.     def size(self):
  146.         "Return the maximum number of bits that can be handled by this key."
  147.         return number.size(self.p) - 1
  148.  
  149.     def has_private(self):
  150.         """Return a Boolean denoting whether the object contains
  151.         private components."""
  152.         if hasattr(self, 'x'):
  153.             return 1
  154.         else:
  155.             return 0
  156.  
  157.     def can_sign(self):
  158.         """Return a Boolean value recording whether this algorithm can generate signatures."""
  159.         return 1
  160.  
  161.     def can_encrypt(self):
  162.         """Return a Boolean value recording whether this algorithm can encrypt data."""
  163.         return 0
  164.  
  165.     def publickey(self):
  166.         """Return a new key object containing only the public information."""
  167.         return construct((self.y, self.g, self.p, self.q))
  168.  
  169. object=DSAobj
  170.  
  171. generate_py = generate
  172. construct_py = construct
  173.  
  174. class DSAobj_c(pubkey):
  175.     keydata = ['y', 'g', 'p', 'q', 'x']
  176.  
  177.     def __init__(self, key):
  178.         self.key = key
  179.  
  180.     def __getattr__(self, attr):
  181.         if attr in self.keydata:
  182.             return getattr(self.key, attr)
  183.         else:
  184.             if self.__dict__.has_key(attr):
  185.                 self.__dict__[attr]
  186.             else:
  187.                 raise AttributeError, '%s instance has no attribute %s' % (self.__class__, attr)
  188.  
  189.     def __getstate__(self):
  190.         d = {}
  191.         for k in self.keydata:
  192.             if hasattr(self.key, k):
  193.                 d[k]=getattr(self.key, k)
  194.         return d
  195.  
  196.     def __setstate__(self, state):
  197.         y,g,p,q = state['y'], state['g'], state['p'], state['q']
  198.         if not state.has_key('x'):
  199.             self.key = _fastmath.dsa_construct(y,g,p,q)
  200.         else:
  201.             x = state['x']
  202.             self.key = _fastmath.dsa_construct(y,g,p,q,x)
  203.  
  204.     def _sign(self, M, K):
  205.         return self.key._sign(M, K)
  206.  
  207.     def _verify(self, M, (r, s)):
  208.         return self.key._verify(M, r, s)
  209.  
  210.     def size(self):
  211.         return self.key.size()
  212.  
  213.     def has_private(self):
  214.         return self.key.has_private()
  215.  
  216.     def publickey(self):
  217.         return construct_c((self.key.y, self.key.g, self.key.p, self.key.q))
  218.  
  219.     def can_sign(self):
  220.         return 1
  221.  
  222.     def can_encrypt(self):
  223.         return 0
  224.  
  225. def generate_c(bits, randfunc, progress_func=None):
  226.     obj = generate_py(bits, randfunc, progress_func)
  227.     y,g,p,q,x = obj.y, obj.g, obj.p, obj.q, obj.x
  228.     return construct_c((y,g,p,q,x))
  229.  
  230. def construct_c(tuple):
  231.     key = apply(_fastmath.dsa_construct, tuple)
  232.     return DSAobj_c(key)
  233.  
  234. if _fastmath:
  235.     #print "using C version of DSA"
  236.     generate = generate_c
  237.     construct = construct_c
  238.     error = _fastmath.error
  239.